﻿#define _CRT_SECURE_NO_WARNINGS 1




#include "List.h"




// OJ链表面试题,3链表的中间结点4链表倒数第k个结点6链表分割7链表回文结构，带头双向循环链表初步






// 
// 3.4 链表面试题
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 1. 删除链表中等于给定值 val 的所有结点。
//		https://leetcode-cn.com/problems/remove-linked-list-elements/description/
// 
// 
// 
// 
// 
// 思路：把不是val的尾插到新链表
// 
// 
// 实现1：不带哨兵位头结点写法
// 
// struct ListNode* removeElements(struct ListNode* head, int val)
//{
//	struct ListNode* cur = head;
//	struct ListNode* newhead = NULL;
//	struct ListNode* tail = NULL;
//
//	while (cur)
//	{
//		if (cur->val != val)
//		{
//			if (tail == NULL)
//			{
//				newhead = tail = cur;
//			}
//			else
//			{
//				tail->next = cur;
//				tail = tail->next;
//			}
//
//			cur = cur->next;
//		}
//		else
//		{
//			struct ListNode* next = cur->next;
//			free(cur);
//			cur = next;
//		}
//	}
//
//	// 排除空指针
//	if (tail)
//		tail->next = NULL;
//
//	return newhead;
//}
//
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 实现2：带哨兵位的头结点写法，方便尾插
// 
// 链表的分类
//		
// 实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
// 
// 带头或者不带头
// 
//		哨兵位头结点，不存储有效数据
// 
// 
// 
// 
// 
//struct ListNode* removeElements(struct ListNode* head, int val)
//{
//	struct ListNode* cur = head;
//
//	struct ListNode* guard, * tail;
//	guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
//	guard->next = NULL;
//
//	while (cur)
//	{
//		if (cur->val != val)
//		{
//			tail->next = cur;
//			tail = tail->next;
//
//			cur = cur->next;
//		}
//		else
//		{
//			struct ListNode* next = cur->next;
//			free(cur);
//			cur = next;
//		}
//	}
//
//	tail->next = NULL;
//
//	// 释放哨兵位头结点
//	struct ListNode* newhead = guard->next;
//	free(guard);
//
//	return newhead;
//}
// 
// 
// 




















// 
// 2. 反转一个单链表。
//		https://leetcode-cn.com/problems/reverse-linked-list/description/
// 
// 
// 
// 
// 
// 思路1：取节点头插
// 
// 
//struct ListNode* reverseList(struct ListNode* head) {
//	struct ListNode* cur = head;
//	struct ListNode* rhead = NULL;
//
//	while (cur)
//	{
//		// 保存下一个需要逆置的节点
//		struct ListNode* next = cur->next;
//
//		// 头插
//		cur->next = rhead;
//		rhead = cur;
//
//		// 更新需要逆置的节点
//		cur = next;
//	}
//	// 返回逆置后的链表
//	return rhead;
//}
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 思路2：三指针反转（直接反转链表的指针方向）
// 
// 
//struct ListNode* reverseList(struct ListNode* head)
//{
//    struct ListNode* n1, * n2, * n3;
//    n1 = NULL;
//    n2 = head;
//
//    while (n2)
//    {
//        // 保存后一个节点地址
//        n3 = n2->next;
//        // 反转链表指针方向
//        n2->next = n1;
//
//        // 向后迭代地址
//        n1 = n2;
//        n2 = n3;
//        if (n3)
//        {
//            // 防止n3为空时解引用
//            n3 = n3->next;
//        }
//    }
//
//    return n1;
//}
// 
//









// 
// 3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
//		https://leetcode-cn.com/problems/middle-of-the-linked-list/description/
// 
// 
// 
// 智力题：烧香问题，一根香烧完60min。
//			计时：15min， 30min， 45min.
// 
// 
// 
// 
// 思路：快慢指针（快指针的遍历速度是慢指针遍历速度的二倍）
// 
// 
// 
//struct ListNode* middleNode(struct ListNode* head)
//{
//    struct ListNode* fast, * slow;
//    fast = slow = head;
//
//    // 偶数结束条件fast = NULL，奇数数结束条件fast->next = NULL
//    while (fast && fast->next)
//    {
//        // 每次向后遍历一个节点
//        slow = slow->next;
//        // 每次向后遍历两个节点
//        fast = fast->next->next;
//    }
//
//    return slow;
//}
// 
// 
// 
// 
// 
// 若当链表为偶数时，需要返回前一个节点，则需要增加prev指针，每次保存slow前一个节点，当fast为NULL结束循环时，则返回prev指针所指向的节点
// 
// 
// 
// 
// 





















// 
// 
// 4. 输入一个链表，输出该链表中倒数第k个结点。
//		https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
// 
// 
// 
// 思路：快慢指针
// 
//	fast先走K步，则终止时fast = NULL
// 
//	fast先走K-1步，则终止时fast->next = NULL
// 
// 
// 经验：
// while(k--)：循环k次
// while(--k)：循环k-1次
// 
// 
// 
//struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
//    // write code here
//
//    struct ListNode* fast, * slow;
//    fast = slow = pListHead;
//
//    // 让fast先走k步
//    while (k--)
//    {
//        // 链表没有k步长
//        if (fast == NULL)
//        {
//            return NULL;
//        }
//
//        fast = fast->next;
//    }
//
//    // fast和slow再向后走
//    while (fast)
//    {
//        fast = fast->next;
//        slow = slow->next;
//    }
//
//
//    return slow;
//}
// 
// 
// 
// 
// 













// 
// 
// 5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。
//		https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
// 
// 
// 
// 
// 
// 思路：双指针取小的尾插
// 
// 实现1：不带哨兵位头结点
// 
// 
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
//{
//	if (list1 == NULL)
//	{
//		return list2;
//	}
//	if (list2 == NULL)
//	{
//		return list1;
//	}
//
//
//	struct ListNode* newhead, * tail;
//	newhead = tail = NULL;
//
//	while (list1 && list2)
//	{
//		if (list1->val < list2->val)
//		{
//			if (tail == NULL)
//			{
//				newhead = tail = list1;
//			}
//			else
//			{
//				tail->next = list1;
//				tail = tail->next;
//			}
//
//			list1 = list1->next;
//		}
//		else
//		{
//			if (tail == NULL)
//			{
//				newhead = tail = list2;
//			}
//			else
//			{
//				tail->next = list2;
//				tail = tail->next;
//			}
//
//			list2 = list2->next;
//		}
//
//	}
//
//	if (list1)
//	{
//		tail->next = list1;
//	}
//	if (list2)
//	{
//		tail->next = list2;
//	}
//
//
//	return newhead;
//}
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 实现2：带哨兵位的头结点
// 
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
//{
//	struct ListNode* guard, * tail;
//	guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
//	guard->next = NULL;
//
//	while (list1 && list2)
//	{
//		if (list1->val < list2->val)
//		{
//			tail->next = list1;
//			tail = tail->next;
//
//			list1 = list1->next;
//		}
//		else
//		{
//			tail->next = list2;
//			tail = tail->next;
//
//			list2 = list2->next;
//		}
//
//	}
//
//	if (list1)
//	{
//		tail->next = list1;
//	}
//	if (list2)
//	{
//		tail->next = list2;
//	}
//
//	// 释放哨兵位的头结点
//	struct ListNode* newhead = guard->next;
//	free(guard);
//
//	return newhead;
//}
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 总结 ---- 如何不用二级指针实现空链表尾插：
// 
// 1.C++引用语法
// 2.哨兵位头结点
// 3.return返回值
// 
// 
// 






















// 
// 
// 6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。
//		https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
// 
// 
// 
// 思路：< x尾插到第一个链表
//		 >=x尾插到第二个链表
//		 两个链表连接起来
// 
// 
// 
// 错误分析：总结分类，
//		1.全部都 >= x，
//		2.全部 < x, 
//		3.有大有小 --- a.最后一个比x大 
//					   b.最后一个比x小，那大链表的最后一个节点的next没有被置位NULL
// 
// 
// 
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        // write code here
//
//        struct ListNode* lessHead, * lessTail, * greaterHead, * greaterTail;
//        lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
//        greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
//        lessTail->next = greaterTail->next = NULL;
//
//        // 循环遍历链表，分别尾插入新的大小链表中
//        struct ListNode* cur = pHead;
//        while (cur)
//        {
//            if (cur->val < x)
//            {
//                lessTail->next = cur;
//                lessTail = lessTail->next;
//            }
//            else
//            {
//                greaterTail->next = cur;
//                greaterTail = greaterTail->next;
//            }
//
//            cur = cur->next;
//        }
//
//        // 链接大小链表
//        lessTail->next = greaterHead->next;
//
//        // 首节点，赋值
//        pHead = lessHead->next;
//        // 尾节点，置空
//        greaterTail->next = NULL;
//
//        // 释放哨兵位节点
//        free(lessHead);
//        free(greaterHead);
//
//        return pHead;
//    }
//};
// 
// 
// 
// 
// 
// 






















// 
// 
// 
// 7. 链表的回文结构。
//		https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
// 
// 
// 
// 思路：翻转链表的后半段，与前半段比较
// 
// 
// 
// 
//class PalindromeList {
//public:
//
//    // 范围链表中间节点
//    struct ListNode* middleNode(struct ListNode* head) {
//        struct ListNode* fast, * slow;
//        fast = slow = head;
//
//        // 偶数结束条件fast = NULL，奇数数结束条件fast->next = NULL
//        while (fast && fast->next) {
//            // 每次向后遍历一个节点
//            slow = slow->next;
//            // 每次向后遍历两个节点
//            fast = fast->next->next;
//        }
//
//        return slow;
//    }
//
//
//    // 翻转一个链表
//    struct ListNode* reverseList(struct ListNode* head) {
//        struct ListNode* cur = head;
//        struct ListNode* rhead = NULL;
//
//        while (cur) {
//            // 保存下一个需要逆置的节点
//            struct ListNode* next = cur->next;
//
//            // 头插
//            cur->next = rhead;
//            rhead = cur;
//
//            // 更新需要逆置的节点
//            cur = next;
//        }
//        // 返回逆置后的链表
//        return rhead;
//    }
//
//
//    // 比较是否符合回文结构
//    bool chkPalindrome(ListNode* A) {
//        // write code here
//        struct ListNode* mid = middleNode(A);
//        struct ListNode* rhead = reverseList(mid);
//
//        // 比较前后部分是否相同
//        while (A && rhead)
//        {
//            if (A->val != rhead->val)
//            {
//                return false;
//            }
//
//            A = A->next;
//            rhead = rhead->next;
//        }
//
//        return true;
//    }
//};
// 
// 
// 
// 
// 
// 
// 
// 





















// 
// 8. 输入两个链表，找出它们的第一个公共结点。
//		https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/
// 
// 
// 9. 给定一个链表，判断链表中是否有环。
//		https://leetcode-cn.com/problems/linked-list-cycle/description/
// 
// 
// 
// 10. 给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL 
//		https://leetcode-cn.com/problems/linked-list-cycle-ii/description/
// 
// 结论
// 让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环
// 运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
// 
// 
// 
// 
// 11. 给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点或空结点。
//		要求返回这个链表的深度拷贝。
// https://leetcode-cn.com/problems/copy-list-with-random-pointer/description/
//
// 
// 
// 12. 其他 。ps：链表的题当前因为难度及知识面等等原因还不适合我们当前学习，以后大家自己
//		下去以后 Leetcode OJ链接 + 牛客 OJ链接
// https://leetcode-cn.com/tag/linked-list/
// https://www.nowcoder.com/activity/oj?title=%E9%93%BE%E8%A1%A8&page=1
// 
// 
// 
// 
// 
// 























// 
// 链表的结构：
//	单			双
//  带头		不带头
//	循环		不循环
// 
// 2*2*2 == 8种链表组合
// 
// 
// 
// 带哨兵位头结点，方便链表尾插
// 
// 不带头单向非循环：结构简单，笔试面试，复杂数据结构的子结构，哈希桶，图的邻接表。
// 
// 带头双向循环链表：结构体最复杂，结构带来使用的便利。
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 单链表为空的重点：结构体必须有，size == 0，capacity都可以
// 
// 不带头不循环单链表表示为空：plist == NULL即可。
// 
// 带头双向循环：必有结构体，哨兵位的头结点的：phead->prev == phead，phead->next == phead
// 
// 
// 
// 
Test1()
{
	LTNode* phead = LTInit();
}


int main()
{
	Test1();

	return 0;
}
// 
// 
// 